package LeetCode.month03.day80;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 16778
 * @date 2025/10/20 8:30
 * @description
 */
public class No210 {
    public int[] res;
    public int index = 0;
    public List<List<Integer>> list = new ArrayList<>();
    public int[] visited;
    public boolean valid = true;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        res = new int[numCourses];
        visited = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            list.add(new ArrayList<>());
        }
        for (int[] prerequisite : prerequisites) {
            list.get(prerequisite[0]).add(prerequisite[1]);
        }
        for (int i = 0; i < numCourses && valid; i++) {
            if(visited[i]==0){
                dfs(i);
            }
        }
        if(!valid) return new int[0];
        return res;
    }

    public void dfs(int x){
        visited[x] = 1;
        for (Integer i : list.get(x)) {
            if(visited[i]==0){
                dfs(i);
                if(!valid){
                    valid = false;
                    return;
                }
            }else if(visited[i]==1){
                valid = false;
                return;
            }
        }
        res[index++]=x;
        visited[x]=2;
    }
}
